package test;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;


/**
 * @author Li Jun Mulin
 * 
 */

public class ForkJoin extends RecursiveAction {
    /**
	 * 
	 */
	private static final long serialVersionUID = 7689426023328857640L;

	final static int ARRAY_LENGTH = 10000000;

    final static int THRESHOLD = 3000000;

    final int[] array;

    final int lo;

    final int hi;

    public ForkJoin(int[] array, int lo, int hi) {
        this.array = array;
        this.lo = lo;
        this.hi = hi;
    }

    private void sequentiallySort(int[] array, int lo, int hi) {
        int[] units = new int[hi - lo + 1];
        for (int i = lo; i <= hi; i++)
            units[i - lo] = array[i];
        Arrays.sort(units);
        for (int i = lo; i <= hi; i++)
            array[i] = units[i - lo];
    }

    private void merge(int[] array, int lo, int mid, int hi) {

        int[] units = new int[hi - lo + 1];
        int i = lo;
        int j = mid + 1;

        for (int k = 0; k < units.length; k++) {
            if (array[i] <= array[j])
                units[k] = array[i++];
            else if (array[i] > array[j])
                units[k] = array[j++];

            if (i > mid)
                for (int m = j; m <= hi; m++)
                    units[++k] = array[m];
            else if (j > hi)
                for (int m = i; m <= mid; m++)
                    units[++k] = array[m];
        }

        for (int k = lo; k <= hi; k++)
            array[k] = units[k - lo];

    }

    protected void compute() {
        try {
            if (hi - lo < THRESHOLD)
                sequentiallySort(array, lo, hi);
            else {
                int mid = (lo + hi) >>> 1;
                System.out.println(mid);
                //fork(new Test(array, lo, mid), new Test(array, mid + 1, hi));
                merge(array, lo, mid, hi);
            }
        } catch (Throwable t) {
            t.printStackTrace();
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] sample = new int[ARRAY_LENGTH];

        System.out.println("Number of processor"
                + Runtime.getRuntime().availableProcessors());
        
        Random seed = new Random(47);

        for (int i = 0; i < sample.length; i++) {
            sample[i] = seed.nextInt();
        }

        long start = System.nanoTime();
        Arrays.sort(sample);
        long duration = System.nanoTime() - start;


        System.out.println("===============Sequential==================");
        System.out.println("Sorting takes " + duration + " to compelte");

        int[] sample2 = new int[ARRAY_LENGTH];

        for (int i = 0; i < sample2.length; i++) {
            sample2[i] = seed.nextInt();
        }

        ForkJoinPool pool = new ForkJoinPool(Runtime.getRuntime()
                .availableProcessors());
        ForkJoin st = new ForkJoin(sample2, 0, sample2.length - 1);

        start = System.nanoTime();
        pool.execute(st);
        while (!st.isDone()) {
        }
        duration = System.nanoTime() - start;

        System.out.println("===============ForkJoin==================");
        System.out.println("Sorting takes " + duration + " to compelte");
        
    }

}